import java.util.Arrays;
import java.util.Scanner;

public class bakerAlg {
    public static int pro_nums;//进程数目
    public static int res_nums;//资源数目
    public static int[] Available;//Available 表示还有多少可用资源

    public static int[][] Max; // Max 表示各进程对资源的最大需求数
    public static int[][] Allocation;//Allocation 表示已经给各进程分配了多少资源
    public static int[][] Need;// Need矩阵表示各进程最多还需要多少资源
    public static int[] Work;// 工作向量 Work,用来表示系统中剩余可用资源数目
    public static int[] Request;//Request表示进程此次申请的各种资源数
    public static int[] SafeSeq;//安全序列

    public static void bankInit(){
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入进程数目：");
        pro_nums=scanner.nextInt();
        System.out.println("请输入资源数目：");
        res_nums=scanner.nextInt();
        Max=new int[pro_nums][res_nums];
        Allocation=new int[pro_nums][res_nums];
        Need=new int[pro_nums][res_nums];
        Work=new int[res_nums];
        Request=new int[res_nums];
        SafeSeq=new int[pro_nums+1];
        Available=new int[res_nums];
        System.out.println("请输入各项最大资源数目：");
        for (int i = 0; i < pro_nums; i++) {
            for (int j = 0; j < res_nums; j++) {
                Max[i][j]=scanner.nextInt();
            }
        }
        System.out.println("请输入各项初始分配资源数目：");
        for (int i = 0; i < pro_nums; i++) {
            for (int j = 0; j < res_nums; j++) {
                Allocation[i][j]=scanner.nextInt();
            }
        }
        //计算需求矩阵
        for (int i = 0; i < pro_nums; i++) {
            for (int j = 0; j < res_nums; j++) {
                Need[i][j]= Max[i][j]-Allocation[i][j];
            }
        }
        System.out.println("请输入各项可用资源数目：");
        for (int i = 0; i < res_nums; i++) {
            Available[i]=scanner.nextInt();
        }
    }
    public static boolean compare(int[] m,int[] n){
        for(int i=0;i<res_nums;i++){
            if(m[i]>n[i]){
                return false;
            }
        }
        return true;
    }

    //判断该状态是否安全(最开始判断初始状态)
    public static boolean isSafe(){
        boolean Finish[]=new boolean[pro_nums];//记录已经结束的进程,若安全，则最终该数组应全部判断为true
        for (int i = 0; i <res_nums ; i++) {
            Work[i]=Available[i];//初始分配让work等于可分配数，不能直接work=available
        }
        int finishNum=0;//结束的进程数目，用于判断循环是否结束
        for (int i = 0; i < pro_nums; i++) {
            if(finishNum==pro_nums){
                break;//保证一次一次判断能判断进程数目次，一旦全部结束，直接返回
            }
            //还未完全结束
            for (int j = 0; j <pro_nums ; j++) {
                //看看是哪个进程没结束
                if(Finish[j]) {
                    continue;
                }else{
                    if(compare(Need[j],Work)){
                        //当需求数目小于剩余数目时，代表可以分配，那么该进程即将结束
                        Finish[j]=true;//进程即将结束
                        SafeSeq[finishNum]=j+1;
                        finishNum++;//结束进程数目+1
                        for (int k = 0; k < res_nums; k++) {
                            Work[k]=Work[k]+Allocation[j][k];//修改可获取资源数目
                        }
                    }
                }
            }
        }
        for (int i = 0; i < pro_nums; i++) {
            if(!Finish[i]){
                return false;
            }
        }

        return true;
    }
    //n代表发出请求的进程号
    public static void reSafe(int n){
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入请求资源数目：");
        for (int i = 0; i <res_nums ; i++) {
            Request[i]=scanner.nextInt();
        }
        //检查此次申请是否超过了之前声明的仍需资源数量,此时系统剩余的可用资源是否还能满足这次请求
        if(compare(Request,Need[n-1])&&compare(Request,Available)){
            for (int i = 0; i < res_nums; i++) {
                Available[i]=Available[i]-Request[i];
                Allocation[n-1][i]=Allocation[n-1][i]+Request[i];
                Need[n-1][i]=Need[n-1][i]-Request[i];
            }
           if(isSafe()){
               System.out.println(Arrays.toString(SafeSeq));
               System.out.println("允许进程"+n+"申请资源");
           }else{
               System.out.println("不允许进程"+n+"申请资源，会导致线程不安全");
               for (int i = 0; i < res_nums; i++) {
                   Available[i]=Available[i]+Request[i];
                   Allocation[n-1][i]=Allocation[n-1][i]-Request[i];
                   Need[n-1][i]=Need[n][i]+Request[i];
               }
           }
        }else{
            System.out.println("申请资源越界");
        }
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        bankInit();
        int n;
        if (isSafe()){
            System.out.println(Arrays.toString(SafeSeq));
            System.out.println("存在安全序列，此时进程安全");
        }else {
            System.out.println("不存在安全序列，此时进程不安全");
            return;
        }
        System.out.println("请输入发出请求的进程编号");
        n=scanner.nextInt();
        reSafe(n);
    }

}
